/*
https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/
*/
class Solution {
public:
    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        string s = to_string(n);
        int m = s.length(),dp[m];
        memset(dp,-1,sizeof(dp));
        //递归函数
        auto dfs = [&](auto&& dfs, int i, bool is_limit, bool is_num) -> int {
            if (i == m) {       
                return is_num; 
            }
            if (!is_limit && is_num && dp[i]>=0) {
                return dp[i]; 
            }
            //res存储答案
            int res = 0;
            if (!is_num) { 
                res = dfs(dfs, i + 1, false, false);
            }
            char up = is_limit ? s[i]: '9';
            for (auto &d:digits) {
                if(d[0]>up) break;
                    res += dfs(dfs, i + 1, is_limit && d[0] == up, true);
            }
            if (!is_limit && is_num) {
                dp[i] = res; 
            }
            return res;
        };
        return dfs(dfs, 0, true, false);
    }
};